package 算法.leetcode.labuladong.数组和链表;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lchenglong
 * @date 2022/6/16
 */
public class 最小覆盖子串 {

    class Solution {

        public String minWindow(String s, String t) {
            Map<Character, Integer> need = new HashMap<>(26);
            Map<Character, Integer> window = new HashMap<>(26);
            for (char c : t.toCharArray()) {
                Integer count = need.get(c);
                if (count == null) need.put(c, 1);
                else need.put(c, ++count);
            }
            int left = 0, right = 0;
            int valid = 0;
            // 记录最⼩覆盖⼦串的起始索引及⻓度
            int start = 0, len = Integer.MAX_VALUE;
            while (right < s.length()) {
                // c 是将移⼊窗⼝的字符
                char c = s.charAt(right);
                // 增⼤窗⼝
                right++;
                // 进⾏窗⼝内数据的⼀系列更新
                if (need.containsKey(c)) {
                    // 窗口中的C的计数+1
                    Integer count = window.get(c);
                    if (count == null) {
                        window.put(c, 1);
                    } else {
                        window.put(c, ++count);
                    }
                    if (window.get(c).equals(need.get(c))) {
                        // c这个字符的个数相同
                        valid++;
                    }
                }
                // 判断左侧窗⼝是否要收缩
                while (valid == need.size()) {
                    // 更新最小覆盖子串
                    if (right - left < len) {
                        start = left;
                        len = right - left;
                    }
                    // d 是将移出窗⼝的字符
                    char d = s.charAt(left);
                    // 缩⼩窗⼝
                    left++;
                    // 进⾏窗⼝内数据的⼀系列更新
                    if (need.containsKey(d)) {
                        if (need.get(d).equals(window.get(d))) {
                            valid--;
                        }
                        window.put(d, window.get(d) - 1);
                    }
                }
            }

            return len == Integer.MAX_VALUE?"":s.substring(start,start+len);
        }
    }
}
